package solutions.leetcode.hard;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/">4. 寻找两个正序数组的中位数</a>
 */
public class Solution4 extends BaseSolution {

    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        float target = ((float) nums1.length + nums2.length + 1) / 2;
        int p1 = -1, p2 = -1;
        float l = Integer.MIN_VALUE;
        while (true) {
            int v1 = p1 + 1 < nums1.length ? nums1[p1 + 1] : Integer.MAX_VALUE;
            int v2 = p2 + 1 < nums2.length ? nums2[p2 + 1] : Integer.MAX_VALUE;
            int last;
            if (v1 <= v2) {
                p1 ++;
                last = v1;
            } else {
                p2 ++;
                last = v2;
            }
            int now = p1 + p2 + 2;
            if (now == target) {
                return last;
            } else {
                if (l != Integer.MIN_VALUE) {
                    return (l + last) / 2;
                } else if (((float) now * 2 + 1) / 2 == target) {
                    l = last;
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        System.out.println(solution.FindMedianSortedArrays(new int[] {
                2
        }, new int[] {

        }));
    }
}